问题背景

在过去的十年里,智能手机已经彻底改变了我们的生活,其方式远远超出了我们的沟通方式。除了打电话、发短信和发电子邮件之外,现在全世界有超过20亿人使用这些设备来预订出租车、比较产品评论和价格、关注新闻、看电影、听音乐、玩视频游戏、拍照、参与社交媒体以及许多其他应用程序。

蜂窝网络是一种手持智能手机网络,其中每一部手机通过蜂窝基站(蜂窝基站)的本地天线通过无线电波与电话网络进行通信。一个重要的问题是手机信号塔的位置,以便为最多的人提供信号覆盖。

问题描述

一家电信公司需要建造一套手机信号塔来为特定城市的居民提供信号覆盖。目前已经确定了几个可能建造信号塔的地点。这些塔有固定的范围,而且由于预算限制,只能建造有限数量的塔。鉴于这些限制,该公司希望尽可能为最大比例的人口提供覆盖。为了简化这个问题,该公司将其希望覆盖的地区划分为一系列区域,每个区域都有已知的人口。接下来的目标是选择公司应该在哪些潜在地点建立手机信号塔,以便为尽可能多的人提供信号覆盖。

数学模型

集合和索引

参数

决策变量

$covered_{j} \in \{0, 1 \}$: This variable is equal to 1 if region $j$ is covered; and 0 otherwise.

$build_{i} \in \{0, 1 \}$: This variable is equal to 1 if tower $i$ is built; and 0 otherwise.

目标函数

约束条件

$$ \begin{equation} \sum_{i \in T} c_{i} \cdot build_{i} \leq \text{budget} \tag{2} \end{equation} $$

数据

信号塔的覆盖情况

Region 0 Region 1 Region 2 Region 3 Region 4 Region 5 Region 6 Region 7 Region 8
Tower 0 1 1 - - - 1 - - -
Tower 1 1 - - - - - - 1 1
Tower 2 - - 1 1 1 - 1 - -
Tower 3 - - 1 - - 1 1 - -
Tower 4 1 - 1 - - - 1 1 1
Tower 5 - - - 1 1 - - - 1

每个区域的人口

Region 0 Region 1 Region 2 Region 3 Region 4 Region 5 Region 6 Region 7 Region 8
Population 523 690 420 1010 1200 850 400 1008 950

信号塔的建设费用

Cost (millions of USD)
Tower 0 4.2
Tower 1 6.1
Tower 2 5.2
Tower 3 5.5
Tower 4 4.8
Tower 5 9.2

预算 $\$20,000,000$.

参考资料: [1] Richard Church and Charles R. Velle. "The Maximal Covering Location Problem". Papers in Regional Science, 1974, vol. 32, issue 1, 101-118.

[2] Tail Assignment Problem. https://www.gurobi.com/case_study/air-france-tail-assignment-optimization/